﻿/// <summary>
/// https://leetcode-cn.com/problems/merge-intervals/
/// </summary>
public class Solution
{
    private interface IIntervals
    {
        IntervalGroup Append(Interval interval);
        IEnumerable<Interval> Split();
    }

    private class Interval : IIntervals
    {
        public int Start { get; }
        public int End { get; }

        public Interval ModifyStart(int newStart)
        {
            return new Interval(newStart, this.End);
        }

        public Interval ModifyEnd(int newEnd)
        {
            return new Interval(this.Start, newEnd);
        }

        public Interval(int start, int end)
        {
            this.Start = start;
            this.End = end;
        }

        public bool Includes(int i)
        {
            return i >= this.Start && i < this.End;
        }

        public IntervalGroup Append(Interval interval)
        {
            return new IntervalGroup().Append(this).Append(interval);
        }

        public IEnumerable<Interval> Split()
        {
            yield return this;
        }
    }

    private class IntervalGroup : IIntervals
    {
        public IntervalGroup()
            : this(Array.Empty<Interval>()) { }
        private IntervalGroup(IEnumerable<Interval> intervals)
        {
            this.intervals = intervals;
        }

        private readonly IEnumerable<Interval> intervals;

        public IntervalGroup Append(Interval interval)
        {
            List<Interval> result = new List<Interval>();
            bool good = false;
            foreach (var current in this.intervals)
            {
                if (good)
                {
                    result.Add(current);
                    continue;
                }

                if (interval.Start > current.End)
                {
                    result.Add(current);
                    continue;
                }
                if (interval.End < current.Start)
                {
                    result.Add(interval);
                    result.Add(current);
                    good = true;
                    continue;
                }
                interval = interval
                    .ModifyStart(Math.Min(interval.Start, current.Start))
                    .ModifyEnd(Math.Max(interval.End, current.End));
            }
            if (!good)
                result.Add(interval);
            return new IntervalGroup(result);
        }

        public IEnumerable<Interval> Split()
        {
            return this.intervals ?? Array.Empty<Interval>();
        }
    }

    public int[][] Merge(int[][] intervals)
    {
        IIntervals result = new IntervalGroup();

        foreach (var interval in intervals)
            result = result.Append(new Interval(interval[0], interval[1]));

        return (from r in result.Split()
                select new int[] { r.Start, r.End })
                .ToArray();
    }
}